home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_08_05 / 8n05098a < prev    next >
Text File  |  1990-04-17  |  2KB  |  77 lines
  1. *****Listing 1*****
  2.  
  3. #include <stdio.h>
  4.  
  5. #define NSTACK    30                /* 2 log2 (max n) */
  6. typedef unsigned int ARRTYPE;    /* type of data to be sorted */
  7.  
  8. void iqsort( n, arr, indx)    /* 1 based arrays */
  9.     unsigned int n;            /* sort arr[1..n] */
  10.     ARRTYPE arr[], *indx[]; /* return indx pointers to sorted arr[] */
  11. {
  12.     static unsigned int stack[NSTACK+1],  llim, rlim, iq, i, j;
  13.     int jstack = 1;            /* "unsigned int" may be faster... */
  14.     static ARRTYPE *a, *b;
  15.     static int swap;
  16.  
  17. /* initialize pointers to input order */
  18.     for( i = 1; i <= n; ++i)
  19.         indx[i] = &arr[i];
  20.  
  21. /* terminate with first pivot element (chosen same as below) */
  22.     indx[n + 1] = indx[((rlim = n) + (llim = 1)) >> 1];
  23.     do
  24.     {                /* while any unsorted segments remain */
  25.         while((int)(rlim - llim) > 1 )
  26.         {        /* 3 or more elements                            */
  27.                 /* quick sort: split segment into 3 segments    */
  28.                 /* pick guess of median element to make segments near equal */
  29.             a = indx[iq = ((i = llim) + (j = rlim)) >> 1];
  30.             indx[iq] = indx[i];
  31.             indx[i] = a;        /* for left terminator */
  32.             for( ; ; )
  33.             {
  34. /* search for small element to be moved to left */
  35.                 while( *a < *(b = indx[j]))
  36.                     --j;
  37.                 if(j <= i)
  38.                     break;
  39.  
  40.                 indx[i] = b;
  41.  
  42. /* search for large element to be moved to right */
  43.                 while( *(b = indx[++i]) < *a )
  44.                     ;
  45.                 if(i >= j)
  46.                 {
  47.                     i = j;
  48.                     break;
  49.                 }
  50.                 indx[j--] = b;
  51.             }
  52.  
  53.             indx[i] = a; /* new middle segment, length 1 */
  54.             if( (jstack += 2) > NSTACK )
  55.                 printf("\nNSTACK exceeded");
  56.  
  57. /* work shorter segment next to limit stacking */
  58.             stack[jstack] = (swap = (rlim-i >= i-llim)) ? rlim : (i-1);
  59.             stack[jstack - 1] = swap ? (i+1) : llim;
  60.             rlim = swap ? (i-1) : rlim;
  61.             llim = swap ? llim : (i+1);
  62.         }
  63.  
  64. /* finish off short segments directly -- optional case for 2 elements */
  65.         if(rlim - llim == 1 && *(a = indx[llim]) > *(b = indx[llim + 1]) )
  66.         {
  67.              indx[llim] = b;
  68.             indx[llim + 1] = a;
  69.         }
  70.  
  71. /* get next segment to sort from stack */
  72.  
  73.         rlim = stack[jstack--];
  74.         llim = stack[jstack--];
  75.     } while(jstack != -1);
  76. }
  77.